package demo.practice.backtrack;

public class Offer47 {

    public static void main(String[] args) {

        Offer47 offer47= new Offer47();
        offer47.maxValue(new int[][]{{1,2,5},{3,2,1}});
    }


    int [][] store;
    public int maxValue(int[][] grid) {
        if (grid == null || grid.length == 0 || grid[0].length == 0)
            return 0;
        store=new int[grid.length][grid[0].length];
        return maxValue(grid, 0, 0);
    }


    public int maxValue(int[][] grid, int i, int j) {

        if(i>=grid.length|| j>=grid[0].length)
            return 0;

        if(store[i][j]!=0)
            return store[i][j];
        int cur = grid[i][j];


        if (i < grid.length-1 && j < grid[0].length-1)
             cur += Math.max(maxValue(grid, i + 1, j), maxValue(grid, i, j + 1));
        else if (i < grid.length-1)
             cur += maxValue(grid, i + 1, j);
        else if (j < grid[0].length-1)
            cur += maxValue(grid, i, j + 1);
//        else
//            cur=cur;

        store[i][j]=cur;
        return store[i][j];
    }
}
